package array;
import java.lang.annotation.Target;
import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;
public class Ex253 {

    public class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }


    /* 
    
    将之前最早结束时间的会议放在堆顶
    若能保证当前开始时间在最早时间之后，则可以节省一个会议室，将之前的最小结束时间会议室出堆，新元素进堆
    若不能，则说明最早结束都不能及时结束，因此不可避免加一
    
    */
    public class Solution { 
        public int minMeetingRooms(Interval[] intervals) { 
            if (intervals.length == 0) return 0;
            Arrays.sort(intervals, (o1, o2) -> o1.start - o2.start);

            Queue<Interval> queue = new PriorityQueue<>((o1, o2) -> o1.end - o2.end);

            int count = 0;

            for (int i = 0; i < intervals.length; i++) {
                if (queue.isEmpty()) {
                    count++;
                } else if (queue.peek().end <= intervals[i].start) {
                    queue.poll();
                } else {
                    count++;
                }
                queue.offer(intervals[i]);
            }

            return queue.size();
        }
    }

    public class Solution1 { 
        public int minMeetingRooms(Interval[] intervals) { 
            if(intervals == null || intervals.length == 0) return 0; 
            int min = 0; int max = 0; 
            //求出start最小值与end最大值
            for(int i=0; i<intervals.length; i++){ 
                min = Math.min(min, intervals[i].start); //？？？min = 0. 因此不可能出现比0小
                max = Math.max(max, intervals[i].end); 
            } 
               
            int[] count = new int[max-min+1]; //创建max end + 1大小的数组 【可能出现0】

            for(int i=0; i<intervals.length; i++){ 
                count[intervals[i].start]++; //对起点位置加一
                count[intervals[i].end]--; //对终点位置减一
            } 
            int maxroom = Integer.MIN_VALUE; 
            int num = 0; 
            for(int i=0; i<count.length; i++){ 
                num += count[i]; 
                maxroom = Math.max(maxroom, num); 
            } 
            return maxroom; 
        } 
    }

    public class Solution2 {
        public int minMeetingRooms(Interval[] intervals) {   
          int n=intervals.length;   
          Arrays.sort(intervals, new Comparator<Interval>(){ 
              public int compare(Interval a, Interval b) {   
                return a.start-b.start;   
              } 
          });   
          PriorityQueue<Integer> pq=new PriorityQueue<>();   
          for (int i=0; i<n; i++) {   
            if (i>0 && intervals[i].start>=pq.peek()) pq.poll();   
            pq.add(intervals[i].end);   
          }   
          return pq.size();   
        }   
      }


    @Test
    public void test() {
        Interval v1 = new Interval(5, 30);
        Interval v2 = new Interval(5, 15);
        Interval v3 = new Interval(15, 20);
        Interval v4 = new Interval(19, 45);
        Interval[] intervals = {v1, v2, v3, v4};
        Solution1 s = new Solution1();
        Solution2 s2 = new Solution2();
        System.out.println(s.minMeetingRooms(intervals));
        System.out.println(s2.minMeetingRooms(intervals));
    }

    @Test
    public void test1() {
        int[] n1 = ArrayGenerator.getArray(100, 100);
        int[] n2 = ArrayGenerator.getArray(100, 100);
        for (int i = 0; i < n2.length; i++) 
            {
                if (n1[i] > n2[i]) {
                int t = n1[i];
                n1[i] = n2[i];
                n2[i] = t;
            }
        }

        Interval[] intervals = new Interval[100];
        for (int i = 0; i < 100; i++) {
            intervals[i] = new Interval(n1[i], n2[i]);
        }

        Solution s = new Solution();
        System.out.println(s.minMeetingRooms(intervals));
        Solution1 s1 = new Solution1();
        System.out.println(s1.minMeetingRooms(intervals));
        Solution2 s2 = new Solution2();
        System.out.println(s2.minMeetingRooms(intervals));
    }
}
